package LeetCode热题HOT100;

public class p338比特位计数 {
    public int[] countBits(int n) {
        //算术找规律
        //偶数1的个数，一定和当前偶数/2的数一样多
        //奇数1的个数，一定等于 它前面紧挨的偶数1的个数+1
        int[] res=new int[n+1];

        for (int i = 1; i <res.length; i++) {
            if (i%2==1) {
                //奇数情况
                res[i]=res[i-1]+1;
            }else {
                //偶数情况
                res[i]=res[i/2];
            }
        }
        return res;
    }

    public int[] countBits2(int n) {
        //动态规划   递归方程 dp[i] = dp[i&(i-1)]+1
        int[] res=new int[n+1];

        for (int i = 1; i <res.length; i++) {
            // i&(i-1) 就可以把 i 的二进制数中，最低位的1去掉
            res[i]=res[i&(i-1)]+1;
        }
        return res;
    }


    public int[] countBits1(int n) {
        //使用Java工具类的内置方法
        int[] res=new int[n+1];

        for (int i = 1; i <res.length; i++) {
            res[i]=Integer.bitCount(i); //bitCount(i)统计 i中 1的个数
        }
        return res;
    }
}
